class Solution {
    public int findKthLargest(int[] nums, int k) {
        sortQuick(0,nums.length-1,nums,k);
        return nums[k-1];
    }
    public int findKthLargest1(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
    private void sortQuick(int left,int right,int[] nums,int k) {
        int startleft = left;
        int startright = right;

        int index = (left+right)/2;
        int tem = nums[index];
        nums[index] = nums[left];
        nums[left] = tem;

        int cur = nums[left];
        int len = nums.length;
        while(left<right) {
            while(left<right && nums[right] <= cur) {
                right--;
            }
            nums[left] = nums[right];
            while(left<right && nums[left] >= cur) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = cur;
        if(left == k-1) {
            return;
        }
        if(left-1 > startleft) {
            sortQuick(startleft,left-1,nums,k);
        }
        if(startright > left+1) {
            sortQuick(left+1,startright,nums,k);
        }
    }
}